Triangle subdivision for triangle meshes ↩

aliases: []
shorthands: {}
created: 2022-02-27 22:13:59
modified: 2022-02-27 22:33:56

The small triangles are created by finding the halving points of the sides of the original triangle, then:

• Create a central small triangle with the halving points as corners
• Create the other three smaller triangles from the corners of the original triangle and the adjacent halving points

The method can be done multiple times of course. These figures show an example, done on a single triangle:

Possible use cases

The method can be done on triangle meshes as well. Possible use cases:

• If we intend to add extra detail to an existing mesh, we just subdivide it a couple of times and us the new vertices to carve the extra detail
• Take the mesh of a regular shape, subdivide its faces, then project the vertices into a sphere we get a sphere with a relatively uniform distribution of vertices (see Sphere mesh from octahedron subdivision and Sphere mesh from icosahedron subdivision)

Algorithm

This algorithm works with the convention of storing the vertex coordinates and indices in separate arrays and is written in Python. The function does multiple passes (determined by the steps argument) by default. Also, this method is not very efficient with memory a lot of vertices become duplicated, maybe even multiple times.

def subdivide_triangles(x, y, z, i, j, k, steps = 4):
    # Create temporary arrays
    x_out = []
    y_out = []
    z_out = []
    i_out = []
    j_out = []
    k_out = []

    for step in range(steps):
        # For every face (traingle), we insert four subtriangles here
        for face in range(len(i)):
            # Calculate halving points into tuples
            half1 = ((x[i[face]] + x[j[face]]) / 2.0, (y[i[face]] + y[j[face]]) / 2.0, (z[i[face]] + z[j[face]]) / 2.0)
            half2 = ((x[j[face]] + x[k[face]]) / 2.0, (y[j[face]] + y[k[face]]) / 2.0, (z[j[face]] + z[k[face]]) / 2.0)
            half3 = ((x[k[face]] + x[i[face]]) / 2.0, (y[k[face]] + y[i[face]]) / 2.0, (z[k[face]] + z[i[face]]) / 2.0)

            # Store corner points in tuples
            p1 = (x[i[face]], y[i[face]], z[i[face]])
            p2 = (x[j[face]], y[j[face]], z[j[face]])
            p3 = (x[k[face]], y[k[face]], z[k[face]])
            # Append the vertices to the vertice arrays, in a fixed order
            x_out.extend([p1[0], p2[0], p3[0], half1[0], half2[0], half3[0]])
            y_out.extend([p1[1], p2[1], p3[1], half1[1], half2[1], half3[1]])
            z_out.extend([p1[2], p2[2], p3[2], half1[2], half2[2], half3[2]])

            plen = len(x_out)

            # Append the indices for the four new triangles
            # The indices are at the end of the vertex arrays, so
            # we subtract from the length of the array
            i_out.extend([plen-6, plen-3, plen-3, plen-2])
            j_out.extend([plen-3, plen-2, plen-5, plen-4])
            k_out.extend([plen-1, plen-1, plen-2, plen-1])

        # Copy the subdivided mesh to the original variable names
        x = [*x_out]
        y = [*y_out]
        z = [*z_out]
        i = [*i_out]
        j = [*j_out]
        k = [*k_out]
        # Reset temporary
        x_out = []
        y_out = []
        z_out = []
        i_out = []
        j_out = []
        k_out = []

    return x, y, z, i, j, k

This algorithm transforms this icosahedron:

Into this (with step = 3):